Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (98,912285)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 98 | |||
Set to 0 | 0 | Set to 1 | 1 | 912285 | Quotient of 98/912285 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 98/912285 | 98 | Quotient of 912285/98 | 9309 |
0 - (9309 x 1) | -9309 | 1 - (9309 x 0) | 1 | Remainder of 912285/98 | 3 | Quotient of 98/3 | 32 |
1 - (32 x -9309) | 297889 | 0 - (32 x 1) | -32 | Remainder of 98/3 | 2 | Quotient of 3/2 | 1 |
-9309 - (1 x 297889) | -307198 | 1 - (1 x -32) | 33 | Remainder of 3/2 | 1 | Quotient of 2/1 | 2 |
297889 - (2 x -307198) | 912285 | -32 - (2 x 33) | -98 | Remainder of 2/1 | 0 | Quotient of 1/0 | 0 |
a = -307198 and b = 33
ax + by = gcd(a,b)
98x + 912285y = gcd(98